package com.lwt.codetop.linkedLists;

// 25. K 个一组翻转链表

/**
 *  思路：1. 判断前驱后是否足够k个，不够则退出循环结束
 *       2. 够k个一组，组内进行翻转
 *       3. 指针指向的改变
 */


// 定义链表结构体

class ListNode {
    int val;
    ListNode next;
    public ListNode(){};
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(int val, ListNode next){
        this.val = val;
        this.next = next;
    }

}

public class ReverseKthOfLinkedList {

    public static void main(String[] args) {
        // 构建测试用例
        int k = 3;
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
//        ListNode newHead = reverseKthOfLikedList(head, 3);
        ListNode newHead = reverseKthOfLikedListNotFullofK(head, k);

        // 输出k个翻转后的新数组
        while(newHead != null){
            System.out.println(newHead.val);
            newHead = newHead.next;
        }

    }

    /**
     * k个一组进行翻转
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKthOfLikedList(ListNode head, int k){
        if(head == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy; // 定义k个一组翻转的前驱

        while(true){
            // 1. 判断前驱后面是否足够k个一组
            ListNode q = p;
            for(int i = 0; i < k; i ++){
                if(q == null) break;
                q = q.next;
            }
            if(q == null) break; // 不足k个
            // 2. 组内翻转，即翻转k-1次
            ListNode a = p.next, b = a.next;
            for(int i = 0; i < k - 1; i ++){
                ListNode c = b.next;
                b.next = a;
                a = b;
                b = c;
            }
            // 3. 改变前后指针指向
            ListNode t = p.next;
            p.next = a;
            t.next = b;
            // 为下次做准备
            p = t;
        }
        return dummy.next;
    }

    /**
     * k个一组进行翻转，最后剩下的不足k个也要进行翻转
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKthOfLikedListNotFullofK(ListNode head, int k){
        if(head == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy; // 定义k个一组翻转的前驱

        Boolean flag = false; // 标记是否够k个


        while(true){
            // 1. 判断前驱后面是否足够k个一组
            ListNode q = p;
            for(int i = 0; i < k; i ++){
                if(q == null) break;
                q = q.next;
            }
            if(q == null){ // 不足k个也要进行翻转
                flag = true;
                break;
            }
            // 2. 组内翻转，即翻转k-1次
            ListNode a = p.next, b = a.next;
            for(int i = 0; i < k - 1; i ++){
                ListNode c = b.next;
                b.next = a;
                a = b;
                b = c;
            }
            // 3. 改变前后指针指向
            ListNode t = p.next;
            p.next = a;
            t.next = b;
            // 为下次做准备
            p = t;
        }

        // 判断是否不足k个（原始/剩下）,不足，再进行翻转剩下的
        if(flag == true && p.next != null){// 不足 且有元素

            ListNode a = p.next, b = a.next;
            while(b != null){
                ListNode c = b.next;
                b.next = a;
                a = b;
                b = c;
            }
            // 改变指针指向
            ListNode t = p.next;
            p.next = a;
            t.next = null; // 最后要置空
        }

        return dummy.next;
    }
}
